<!DOCTYPE html>




<html class="theme-next pisces" lang="zh-CN">
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="theme-color" content="#222">













<meta http-equiv="Cache-Control" content="no-transform">
<meta http-equiv="Cache-Control" content="no-siteapp">


















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css">


<link href="https://fonts.loli.net/css?family=EB+Garamond:400,400i,700,700i|Noto+Serif+SC:400,500,700&display=swap&subset=chinese-simplified" rel="stylesheet">




  

<link href="//cdn.jsdelivr.net/npm/font-awesome@4.7.0/css/font-awesome.min.css" rel="stylesheet" type="text/css">

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=5.1.4">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="C++,">





  <link rel="alternate" href="/atom.xml" title="孔明の博客" type="application/atom+xml">






<meta name="description" content="DDA、中点画线、Bresenham算法">
<meta name="keywords" content="C++">
<meta property="og:type" content="article">
<meta property="og:title" content="扫描转换算法">
<meta property="og:url" content="https://gkm0120.github.io/p/09543.html">
<meta property="og:site_name" content="孔明の博客">
<meta property="og:description" content="DDA、中点画线、Bresenham算法">
<meta property="og:locale" content="zh-CN">
<meta property="og:image" content="https://cdn.jsdelivr.net/gh/gkm0120/CDN/images/2020033101.jpg">
<meta property="og:image" content="https://cdn.jsdelivr.net/gh/gkm0120/CDN/images/2020033102.jpg">
<meta property="og:image" content="https://cdn.jsdelivr.net/gh/gkm0120/CDN/images/2020040305.jpg">
<meta property="og:image" content="https://cdn.jsdelivr.net/gh/gkm0120/CDN/images/2020040301.jpg">
<meta property="og:image" content="https://cdn.jsdelivr.net/gh/gkm0120/CDN/images/2020040302.jpg">
<meta property="og:image" content="https://cdn.jsdelivr.net/gh/gkm0120/CDN/images/2020040303.jpg">
<meta property="og:image" content="https://cdn.jsdelivr.net/gh/gkm0120/CDN/images/2020033103.jpg">
<meta property="og:image" content="https://cdn.jsdelivr.net/gh/gkm0120/CDN/images/2020033104.jpg">
<meta property="og:image" content="https://cdn.jsdelivr.net/gh/gkm0120/CDN/images/2020033107.jpg">
<meta property="og:image" content="https://cdn.jsdelivr.net/gh/gkm0120/CDN/images/2020040306.jpg">
<meta property="og:image" content="https://cdn.jsdelivr.net/gh/gkm0120/CDN/img/20200416202043.png">
<meta property="og:image" content="https://cdn.jsdelivr.net/gh/gkm0120/CDN/img/20200416204239.png">
<meta property="og:updated_time" content="2021-04-05T01:47:55.861Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="扫描转换算法">
<meta name="twitter:description" content="DDA、中点画线、Bresenham算法">
<meta name="twitter:image" content="https://cdn.jsdelivr.net/gh/gkm0120/CDN/images/2020033101.jpg">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Pisces',
    version: '5.1.4',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":false,"scrollpercent":true,"onmobile":true},
    fancybox: true,
    tabs: true,
    motion: {"enable":false,"async":false,"transition":{"post_block":"flipYIn","post_header":"perspectiveRightIn","post_body":"perspectiveLeftIn","coll_header":"perspectiveDownIn","sidebar":"perspectiveUpIn"}},
    duoshuo: {
      userId: '0',
      author: 'Author'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="https://gkm0120.github.io/p/09543.html">





<!-- 设置文章需要密码访问 -->
<script>
    (function(){
        if(''){
            if (prompt('请输入文章密码') !== ''){
                alert('密码错误！');
                history.back();
            }
        }
    })();
</script>

  <title>扫描转换算法 | 孔明の博客</title>

  

  








<link rel="stylesheet" href="/css/prism-tomorrow.css" type="text/css">
<link rel="stylesheet" href="/css/prism-line-numbers.css" type="text/css"></head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-CN">

  

  
  
    
  

  <div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <!--fork me from github-->
    <a href="https://github.com/gkm0120" class="github-corner" aria-label="View source on GitHub"><svg width="80" height="80" viewbox="0 0 250 250" style="fill:#64CEAA; color:#fff; position: absolute; top: 0; border: 0; right: 0;" aria-hidden="true"><path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"/><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"/><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"/></svg></a><style>.github-corner:hover .octo-arm{animation:octocat-wave 560ms ease-in-out}@keyframes octocat-wave{0%,100%{transform:rotate(0)}20%,60%{transform:rotate(-25deg)}40%,80%{transform:rotate(10deg)}}@media (max-width:500px){.github-corner:hover .octo-arm{animation:none}.github-corner .octo-arm{animation:octocat-wave 560ms ease-in-out}}</style>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">孔明の博客</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <h1 class="site-subtitle" itemprop="description"></h1>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br>
            
            Home
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br>
            
            Archives
          </a>
        </li>
      

      
        <li class="menu-item menu-item-search">
          
            <a href="javascript:;" class="popup-trigger">
          
            
              <i class="menu-item-icon fa fa-search fa-fw"></i> <br>
            
            Search
          </a>
        </li>
      
    </ul>
  

  
    <div class="site-search">
      
  <div class="popup search-popup local-search-popup">
  <div class="local-search-header clearfix">
    <span class="search-icon">
      <i class="fa fa-search"></i>
    </span>
    <span class="popup-btn-close">
      <i class="fa fa-times-circle"></i>
    </span>
    <div class="local-search-input-wrapper">
      <input autocomplete="off" placeholder="Searching..." spellcheck="false" type="text" id="local-search-input">
    </div>
  </div>
  <div id="local-search-result"></div>
</div>



    </div>
  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://gkm0120.github.io/p/09543.html">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="戈孔明">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="孔明の博客">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">扫描转换算法</h2>
        

        <div class="post-meta">
          <span class="post-time">

             

             

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2020-03-31T16:33:52+08:00">
                2020-03-31
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">In</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/图形图像处理/" itemprop="url" rel="index">
                    <span itemprop="name">图形图像处理</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          <!--
          
          -->

          
            <span class="post-wordcount">
              
                
                  <span class="post-meta-divider">|</span>
                
                <span class="post-meta-item-icon">
                  <i class="fa fa-file-word-o"></i>
                </span>
                
                <span title="Words count in article">
                  2.9k
                </span>
              

              
                <span class="post-meta-divider">|</span>
              

              
                <span class="post-meta-item-icon">
                  <i class="fa fa-clock-o"></i>
                </span>
                
                <span title="Reading time">
                  12 分钟
                </span>
              
            </span>
          

          <!-- 隐藏文章内标题下，内容描述
          
          -->

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <p>DDA、中点画线、Bresenham算法</p>
<a id="more"></a>

<h2 id="1-直线扫描转换算法"><a href="#1-直线扫描转换算法" class="headerlink" title="1 直线扫描转换算法"></a>1 直线扫描转换算法</h2><h3 id="1-1-DDA算法"><a href="#1-1-DDA算法" class="headerlink" title="1.1 DDA算法"></a>1.1 DDA算法</h3><blockquote>
<p>Digital Differential Analyer</p>
</blockquote>
<p>在计算机光栅显示器上绘制一条直线$ y=kx+b $的本质是用一些离散的像素点去逼近这条直线，需要确定这些像素点的$ x $，$ y $坐标。<br><img width="300" height="200" src="https://cdn.jsdelivr.net/gh/gkm0120/CDN/images/2020033101.jpg"></p>
<p>给出确定的两个端点$ \bigl(x_0,y_0\bigr) $和$ \bigl(x_1,y_1\bigr) $，即斜率$ k=\frac{y_1-y_0}{x_1-x_0} $<br>现假定$ x $已知，即从起点$ x_0 $开始，沿$ x $方向前进一个像素（步长=1），可以计算相应的$ y $值</p>
<blockquote>
<p>注：因为像素的坐标是整数，而斜率$k$是浮点数，所以对于计算出的$ y $值需要进行取整处理</p>
</blockquote>
<ol>
<li>基本思想：</li>
</ol>
<ul>
<li>$ k\le1 $时，对$ x $值计算相应的$ y $值（对$ y $取整），从而确定需要给那些像素着色</li>
<li>$ k&gt;1 $时，对$ y $值计算相应的$ x $值（对$ x $取整），从而确定需要给那些像素着色</li>
</ul>
<img width="200" height="200" src="https://cdn.jsdelivr.net/gh/gkm0120/CDN/images/2020033102.jpg">

<ol start="2">
<li>优化计算思想：增量思想</li>
</ol>
<ul>
<li>$ k\le1 $时,对于 $ y_i=kx_i+b $，$ y_{i+1}=kx_{i+1}+b=k(x_i+1)+b=y_i+k $，那么斜率$ k $即可看为前进一步的增量，这样就把将乘法运算变成了加法</li>
<li>$ k&gt;1 $时，取$ x_{i+1}=x_i+\frac{1}{k} $即可</li>
</ul>
<h4 id="1-1-1-代码"><a href="#1-1-1-代码" class="headerlink" title="1.1.1 代码"></a>1.1.1 代码</h4><div class="highlight-wrap" autocomplete="off" autocorrect="off" autocapitalize="off" spellcheck="false" contenteditable="true" data-rel="CPP"><figure class="iseeu highlight /cpp"><table><tbody><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;GL\glut.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cmath&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">init</span><span class="params">(<span class="keyword">void</span>)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line">    glClearColor(<span class="number">1.0</span>, <span class="number">1.0</span>, <span class="number">1.0</span>, <span class="number">0.0</span>);  <span class="comment">// Set display-window color to white.</span></span><br><span class="line">    glMatrixMode(GL_PROJECTION);       <span class="comment">// Set projection parameters.</span></span><br><span class="line">    gluOrtho2D(<span class="number">0.0</span>, <span class="number">200.0</span>, <span class="number">0.0</span>, <span class="number">150.0</span>);</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">    数值微分方法画线</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">LineDDA</span><span class="params">(<span class="keyword">int</span> x1, <span class="keyword">int</span> y1, <span class="keyword">int</span> x2, <span class="keyword">int</span> y2)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line">    glColor3f(<span class="number">1.0</span>, <span class="number">0.0</span>, <span class="number">0.0</span>);       <span class="comment">// 红色</span></span><br><span class="line">    glPointSize(<span class="number">2.0f</span>);</span><br><span class="line"></span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">        两点重合尚未判断</span></span><br><span class="line"><span class="comment">    */</span></span><br><span class="line">    <span class="keyword">int</span> dm = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">if</span> (<span class="built_in">abs</span>(x2 - x1) &gt;= <span class="built_in">abs</span>(y2 - y1))</span><br><span class="line">    {</span><br><span class="line">        dm = <span class="built_in">abs</span>(x2 - x1);              <span class="comment">// x 为计长方向</span></span><br><span class="line">    }</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    {</span><br><span class="line">        dm = <span class="built_in">abs</span>(y2 - y1);              <span class="comment">// y 为计长方向</span></span><br><span class="line">    }</span><br><span class="line">    <span class="keyword">float</span> dx = (<span class="keyword">float</span>)(x2 - x1) / dm;   <span class="comment">// 当 x 为计长方向，dx = 1</span></span><br><span class="line">    <span class="keyword">float</span> dy = (<span class="keyword">float</span>)(y2 - y1) / dm;   <span class="comment">// 当 y 为计长方向，dy = 1</span></span><br><span class="line">    <span class="keyword">float</span> x = x1;</span><br><span class="line">    <span class="keyword">float</span> y = y1;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; dm; ++i)</span><br><span class="line">    {</span><br><span class="line">        glBegin(GL_POINTS);</span><br><span class="line">        glVertex2f((<span class="keyword">int</span>)x, (<span class="keyword">int</span>)y);</span><br><span class="line">        glEnd();</span><br><span class="line">        glFlush();</span><br><span class="line">        x += dx;</span><br><span class="line">        y += dy;</span><br><span class="line">    }</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">    交换两个int 类型的变量的值</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">swap_value</span><span class="params">(<span class="keyword">int</span>* a, <span class="keyword">int</span>* b)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line">    <span class="keyword">int</span> tmp = *a;</span><br><span class="line">    *a = *b;</span><br><span class="line">    *b = tmp;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">// 窗口大小改变时调用的登记函数</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">ChangeSize</span><span class="params">(GLsizei w, GLsizei h)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (h == <span class="number">0</span>)     h = <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 设置视区尺寸</span></span><br><span class="line">    glViewport(<span class="number">0</span>, <span class="number">0</span>, w, h);</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 重置坐标系统</span></span><br><span class="line">    glMatrixMode(GL_PROJECTION);</span><br><span class="line">    glLoadIdentity();</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 建立修剪空间的范围</span></span><br><span class="line">    <span class="keyword">if</span> (w &lt;= h)</span><br><span class="line">        glOrtho(<span class="number">0.0f</span>, <span class="number">250.0f</span>, <span class="number">0.0f</span>, <span class="number">250.0f</span>*h / w, <span class="number">1.0</span>, <span class="number">-1.0</span>);</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">        glOrtho(<span class="number">0.0f</span>, <span class="number">250.0f</span>*w / h, <span class="number">0.0f</span>, <span class="number">250.0f</span>, <span class="number">1.0</span>, <span class="number">-1.0</span>);</span><br><span class="line"></span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">display</span><span class="params">(<span class="keyword">void</span>)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line">    <span class="comment">// 用当前背景色填充窗口，如果不写这句会残留之前的图像</span></span><br><span class="line">    glClear(GL_COLOR_BUFFER_BIT);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> x1 = <span class="number">20</span>, y1 = <span class="number">20</span>, x2 = <span class="number">160</span>, y2 = <span class="number">80</span>;</span><br><span class="line">    LineDDA(x1, y1, x2, y2);</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">(<span class="keyword">int</span> argc, <span class="keyword">char</span>* argv[])</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line">    glutInit(&amp;argc, argv);</span><br><span class="line">    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);</span><br><span class="line">    glutInitWindowPosition(<span class="number">200</span>, <span class="number">200</span>);</span><br><span class="line">    glutInitWindowSize(<span class="number">400</span>, <span class="number">400</span>);</span><br><span class="line">    glutCreateWindow(<span class="string">"Line"</span>);</span><br><span class="line">    glutDisplayFunc(display);</span><br><span class="line">    glutReshapeFunc(ChangeSize);</span><br><span class="line">    init();</span><br><span class="line">    glutMainLoop();</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></tbody></table></figure></div>

<h4 id="1-1-2-运行结果"><a href="#1-1-2-运行结果" class="headerlink" title="1.1.2 运行结果"></a>1.1.2 运行结果</h4><img width="300" height="200" src="https://cdn.jsdelivr.net/gh/gkm0120/CDN/images/2020040305.jpg">


<h3 id="1-2-中点画线算法"><a href="#1-2-中点画线算法" class="headerlink" title="1.2 中点画线算法"></a>1.2 中点画线算法</h3><blockquote>
<p>效率上最快</p>
</blockquote>
<p>基本思想：采用直线的一般式方程$ F(x,y)=Ax+By+C=0 $<br>$ F(x,y)=Ax+By+C=0\le\left|k\right|\le1 $,$ x_i+1\rightarrow y_i \rightarrow \begin{cases}y_i \\y_i +1\end{cases}$，把浮点运算改成整数加法。</p>
<p>假定$ 0\le\left|k\right|\le1 $，沿$x$方向前进一个像素，$x_i \rightarrow x_i+1$，计算出$y_i \rightarrow \begin{cases}y_i \\y_i +1\end{cases} $.</p>
<ul>
<li>当中点$M$在$Q$下方时，则$P_u$离直线近一些，选择$P_u$作为下一个像素点</li>
<li>当中点$M$在$Q$上方时，则$P_d$离直线近一些，选择$P_d$作为下一个像素点</li>
</ul>
<img width="300" height="200" src="https://cdn.jsdelivr.net/gh/gkm0120/CDN/images/2020040301.jpg">

<p>判断$M$与$Q$的位置关系：将$M$点坐标代入方程有$d_i=A(x_i+1)+B(y_i+0.5)+C$</p>
<ul>
<li>当$d_i\geq0$时选择$P_d$</li>
<li>当$d_i&lt;0$时选择$P_u$</li>
</ul>
<img width="300" height="200" src="https://cdn.jsdelivr.net/gh/gkm0120/CDN/images/2020040302.jpg">

<p>优化计算：$p(x_i,y_i)$在直线上即$Ax_i+By_i+C=0$，初值$d_0=F\left(x_i+1,y_i+0.5\right)=A+0.5B$</p>
<ul>
<li><p>当选择了$P_u$作为像素点时，$d_0=F\left(x_i+1,y_i+0.5\right)$；$d_1=F\left(x_i+2,y_i+1.5\right)=d_0+A+B$</p>
</li>
<li><p>当选择了$P_d$作为像素点时，$d_0=F\left(x_i+1,y_i+0.5\right)$；$d_1=F\left(x_i+2,y_i+0.5\right)=d_0+A$</p>
</li>
</ul>
<img width="300" height="200" src="https://cdn.jsdelivr.net/gh/gkm0120/CDN/images/2020040303.jpg">

<h2 id="Bresenham算法"><a href="#Bresenham算法" class="headerlink" title="Bresenham算法"></a>Bresenham算法</h2><blockquote>
<p>适用范围扩大，与方程无关不仅限于画直线</p>
</blockquote>
<h3 id="1-3-理论"><a href="#1-3-理论" class="headerlink" title="1.3 理论"></a>1.3 理论</h3><p>DDA算法在编码实现比较容易，但是每生成一个像素都要用到一次浮点加法运算，Bresenham的线段光栅化算法可以避免浮点运算。</p>
<ol>
<li>假设线段的起点$ \bigl(x_0,y_0\bigr) $和终点$ \bigl(x_1,y_1\bigr) $的坐标值都是整数，且斜率满足$ 0\leq m\leq 1 $</li>
<li>在线段扫描转换过程某一步中，假定已知$ (i+\frac{1}{2},j+\frac{1}{2}) $的像素。该线段所在的直线方程为$ y=mx+h $,当$ x=i+\frac{1}{2} $时，该直线与$ (i+\frac{1}{2},j+\frac{1}{2}) $处像素的垂直扫描线的实际交点是在垂直扫描线上位于该像素的半个像素内部的某一点（假定像素中心位置的坐标值位于两个整数之间），否则，对该实际交点进行四舍五入处理后不可能得到当前这个像素。</li>
</ol>
<img width="200" height="200" src="https://cdn.jsdelivr.net/gh/gkm0120/CDN/images/2020033103.jpg">

<ol start="3">
<li>可以引入判定变量$ d=b-a $来判断下一个像素点的坐标，其中，$ a $和$ b $<br>表示在$x=i+\frac{3}{2}$号处，该线段分别离上方候选像素和下方候选像素的距离，如果$ d&lt;0 $，那么线段靠近下方的像素，所以选择位于$ (x=i+\frac{3}{2},j+\frac{1}{2}) $处的下方像素；否则，应选择位于$ (i+\frac{3}{2},j+\frac{3}{2}) $处的上方像素.</li>
</ol>
<img width="200" height="200" src="https://cdn.jsdelivr.net/gh/gkm0120/CDN/images/2020033104.jpg">

<h4 id="1-3-1-优化"><a href="#1-3-1-优化" class="headerlink" title="1.3.1 优化"></a>1.3.1 优化</h4><blockquote>
<p>定点运算代替浮点运算</p>
</blockquote>
<p>令$ d=(x_2-x_1)(b-a)=\Delta x(b-a) $，用线段的方程将$ a $和$ b $的值代入，结合$ m=\frac{y_2-y_1}{x_2-x_1} $，$ h=y_2-mx_2 $，运算得$ d $为一整数（用到多次定点运算）</p>
<blockquote>
<p>使该算法成为增量算法</p>
</blockquote>
<p>假定$ d_k $是$ x＝k+\frac{1}{2} $号时对应的$ d $值。我们希望计算$ d_k $的增量形$ d_k+1 $，它是$ x=k+\frac{3}{2} $号时对应的$ d $值。</p>
<p>通过观察上方候选像素与直线之间的距离$ a $的值，当$ x=k+\frac{1}{2} $处像素的 $ y $坐标相对于前一个像素增加1，$ a $值增加$ 1-m $，或者减少$ m $。同理，当增加$ x $的值时，$ b $值要么增加$ m $，要么减少$ 1-m $。</p>
<img width="300" height="200" src="https://cdn.jsdelivr.net/gh/gkm0120/CDN/images/2020033107.jpg">

<p>其中：<br>        $$d_{k+1}=\begin{cases}<br>    d_k+2\Delta y \qquad &amp; d_k&lt;0\\<br>    2(\Delta y-\Delta x)\qquad &amp; d_k\geq0<br>    \end{cases} $$</p>
<h4 id="1-3-2-代码"><a href="#1-3-2-代码" class="headerlink" title="1.3.2 代码"></a>1.3.2 代码</h4><div class="highlight-wrap" autocomplete="off" autocorrect="off" autocapitalize="off" spellcheck="false" contenteditable="true" data-rel="CPP"><figure class="iseeu highlight /cpp"><table><tbody><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;windows.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;GL/glu.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;GL/gl.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;GL/glut.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;GL\glut.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cmath&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">init</span><span class="params">(<span class="keyword">void</span>)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line">    glClearColor(<span class="number">1.0</span>, <span class="number">1.0</span>, <span class="number">1.0</span>, <span class="number">0.0</span>);  <span class="comment">// Set display-window color to white.</span></span><br><span class="line">    glMatrixMode(GL_PROJECTION);       <span class="comment">// Set projection parameters.</span></span><br><span class="line">    gluOrtho2D(<span class="number">0.0</span>, <span class="number">200.0</span>, <span class="number">0.0</span>, <span class="number">150.0</span>);</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">    交换两个int 类型的变量的值</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">swap_value</span><span class="params">(<span class="keyword">int</span>* a, <span class="keyword">int</span>* b)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line">    <span class="keyword">int</span> tmp = *a;</span><br><span class="line">    *a = *b;</span><br><span class="line">    *b = tmp;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">    Bresenham 画线法</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">LineBres</span><span class="params">(<span class="keyword">int</span> x1, <span class="keyword">int</span> y1, <span class="keyword">int</span> x2, <span class="keyword">int</span> y2)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line">    glColor3f(<span class="number">0.0</span>, <span class="number">0.0</span>, <span class="number">1.0</span>);       <span class="comment">// 蓝色</span></span><br><span class="line">    glPointSize(<span class="number">2.0f</span>);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> dx = <span class="built_in">abs</span>(x2 - x1);</span><br><span class="line">    <span class="keyword">int</span> dy = <span class="built_in">abs</span>(y2 - y1);</span><br><span class="line">    <span class="comment">// 两点重合</span></span><br><span class="line">    <span class="keyword">if</span> (dx == <span class="number">0</span> &amp;&amp; dy == <span class="number">0</span>)</span><br><span class="line">    {</span><br><span class="line">        glBegin(GL_POINTS);</span><br><span class="line">            glVertex2f(x1, y1);</span><br><span class="line">        glEnd();</span><br><span class="line">        glFlush();</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    }</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> flag = <span class="number">0</span>;       <span class="comment">// 将斜率变换到 0 &lt;= |k| &lt;= 1 区间</span></span><br><span class="line">    <span class="keyword">if</span> (dx &lt; dy)</span><br><span class="line">    {</span><br><span class="line">        flag = <span class="number">1</span>;</span><br><span class="line">        swap_value(&amp;x1, &amp;y1);</span><br><span class="line">        swap_value(&amp;x2, &amp;y2);</span><br><span class="line">        swap_value(&amp;dx, &amp;dy);</span><br><span class="line">    }</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> tx = (x2 - x1) &gt; <span class="number">0</span> ? <span class="number">1</span> : <span class="number">-1</span>;</span><br><span class="line">    <span class="keyword">int</span> ty = (y2 - y1) &gt; <span class="number">0</span> ? <span class="number">1</span> : <span class="number">-1</span>;</span><br><span class="line">    <span class="keyword">int</span> curx = x1;</span><br><span class="line">    <span class="keyword">int</span> cury = y1;</span><br><span class="line">    <span class="keyword">int</span> dS = <span class="number">2</span> * dy;</span><br><span class="line">    <span class="keyword">int</span> dT = <span class="number">2</span> * (dy - dx);</span><br><span class="line">    <span class="keyword">int</span> d = dS - dx;</span><br><span class="line">    <span class="keyword">while</span> (curx != x2)</span><br><span class="line">    {</span><br><span class="line">        <span class="keyword">if</span> (d &lt; <span class="number">0</span>)</span><br><span class="line">            d += dS;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">        {</span><br><span class="line">            cury += ty;</span><br><span class="line">            d += dT;</span><br><span class="line">        }</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span> (flag)</span><br><span class="line">        {</span><br><span class="line">            glBegin(GL_POINTS);</span><br><span class="line">                glVertex2f(cury, curx);</span><br><span class="line">            glEnd();</span><br><span class="line">            glFlush();</span><br><span class="line">        }</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">        {</span><br><span class="line">            glBegin(GL_POINTS);</span><br><span class="line">                glVertex2f(curx, cury);</span><br><span class="line">            glEnd();</span><br><span class="line">            glFlush();</span><br><span class="line">        }</span><br><span class="line">        curx += tx;</span><br><span class="line">    }</span><br><span class="line"></span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">// 窗口大小改变时调用的登记函数</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">ChangeSize</span><span class="params">(GLsizei w, GLsizei h)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (h == <span class="number">0</span>)     h = <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 设置视区尺寸</span></span><br><span class="line">    glViewport(<span class="number">0</span>, <span class="number">0</span>, w, h);</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 重置坐标系统</span></span><br><span class="line">    glMatrixMode(GL_PROJECTION);</span><br><span class="line">    glLoadIdentity();</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 建立修剪空间的范围</span></span><br><span class="line">    <span class="keyword">if</span> (w &lt;= h)</span><br><span class="line">        glOrtho(<span class="number">0.0f</span>, <span class="number">250.0f</span>, <span class="number">0.0f</span>, <span class="number">250.0f</span>*h / w, <span class="number">1.0</span>, <span class="number">-1.0</span>);</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">        glOrtho(<span class="number">0.0f</span>, <span class="number">250.0f</span>*w / h, <span class="number">0.0f</span>, <span class="number">250.0f</span>, <span class="number">1.0</span>, <span class="number">-1.0</span>);</span><br><span class="line"></span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">display</span><span class="params">(<span class="keyword">void</span>)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line">    <span class="comment">// 用当前背景色填充窗口，如果不写这句会残留之前的图像</span></span><br><span class="line">    glClear(GL_COLOR_BUFFER_BIT);</span><br><span class="line">    <span class="keyword">int</span> x12 = <span class="number">20</span>, y12 = <span class="number">40</span>, x22 = <span class="number">160</span>, y22 = <span class="number">100</span>;</span><br><span class="line">    LineBres(x12, y12, x22, y22);</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">(<span class="keyword">int</span> argc, <span class="keyword">char</span>* argv[])</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line">    glutInit(&amp;argc, argv);</span><br><span class="line">    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);</span><br><span class="line">    glutInitWindowPosition(<span class="number">200</span>, <span class="number">200</span>);</span><br><span class="line">    glutInitWindowSize(<span class="number">400</span>, <span class="number">400</span>);</span><br><span class="line">    glutCreateWindow(<span class="string">"Line"</span>);</span><br><span class="line">    glutDisplayFunc(display);</span><br><span class="line">    glutReshapeFunc(ChangeSize);</span><br><span class="line">    init();</span><br><span class="line">    glutMainLoop();</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></tbody></table></figure></div>

<h4 id="1-3-3-运行结果"><a href="#1-3-3-运行结果" class="headerlink" title="1.3.3 运行结果"></a>1.3.3 运行结果</h4><img width="300" height="200" src="https://cdn.jsdelivr.net/gh/gkm0120/CDN/images/2020040306.jpg">

<h2 id="2-多边形扫描转化算法"><a href="#2-多边形扫描转化算法" class="headerlink" title="2 多边形扫描转化算法"></a>2 多边形扫描转化算法</h2><p>多边形分为凸多边形，凹多边形（任意两顶点间的连线有不在多边形内的部分）含内环的多边形</p>
<h3 id="2-1-X扫描线算法"><a href="#2-1-X扫描线算法" class="headerlink" title="2.1 X扫描线算法"></a>2.1 X扫描线算法</h3><blockquote>
<p>多边形扫描转换指的是把多边形的顶点表示转换为点阵表示</p>
</blockquote>
<ol>
<li>基本思想：按扫描线的顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素，完成填充工作。端点即为扫描线与多边形边界线的交点。</li>
<li>算法步骤：</li>
</ol>
<img width="300" height="200" src="https://cdn.jsdelivr.net/gh/gkm0120/CDN/img/20200416202043.png">

<p>（1） 确定多边形所占有的最大扫描数，得到多边形顶点的最小和最大值<br>（2） 从 $y=y_{min}$ 到 $y=y_{max}$ 每次用一条扫描线进行填充<br>（3） 扫描线的填充过程：求交排序（交点按递增顺序排）$\to$交点配对（偶数个）$\to$区间填色</p>
<ol start="3">
<li>当扫描线与某一顶点相交时，交点的取舍问题处理办法为：<br>共享顶点的两条边分别落在扫描线左右两边，交点只算1个<br>共享顶点的两条边的另外两个端点 值大于顶点 值，交点算2个，否则算0个<br>缺点：扫描线与多边形各边求交很麻烦</li>
</ol>
<h3 id="2-2-改进的X扫描线算法（不求交）"><a href="#2-2-改进的X扫描线算法（不求交）" class="headerlink" title="2.2 改进的X扫描线算法（不求交）"></a>2.2 改进的X扫描线算法（不求交）</h3><ol>
<li><p>改进求交方法：<br>（1）只与有效边求交；<br>（2）扫描线的连贯性——当前扫描线与各边交点顺序与下条扫描线与各边交点顺序雷同;<br>（3）多边形的连贯性——某条边与当前扫描线相交时很可能也与下一条扫描线相交.</p>
</li>
<li><p>引进数据结构：<br>（1）活性边表——与当前扫描线相交的边叫做活性边，并把他们按与扫描线交点，坐标递增的顺序存放在一个链表中<br>（2）结点内容——$x$（交点坐标）；$\delta{x}$（相邻扫描线的增量）；$y_{max}$（最高扫描线的坐标值）</p>
</li>
</ol>
<p>$$ x  \to \delta x \to y_{max} \to \text { Next } $$</p>
<p> 扫描线一次向上移动1，即$y_{i+1}-y_{i}=1$ ，相交直线边斜率为$k$，即$x_{i+1}=x_{i}+\frac{1}{k}$<br>其中$\delta=\frac{1}{k}$ ，而$y_{max}$可以确定何时抛弃该有效边</p>
<ol start="3">
<li>构建新边表：构造纵向链表，链表长度为多边形所占有的最大扫描线数<br>对扫描线出现的位置构造</li>
</ol>
<p>$$ y_{max} \to x_{min} \to \frac{1}{k} \to \text { Next } $$</p>
<img width="300" height="200" src="https://cdn.jsdelivr.net/gh/gkm0120/CDN/img/20200416204239.png">

<p>注：边是否被抛弃，未抛弃则要注意 ，还要看是否有新边进来</p>
<h3 id="2-3-区域填充算法"><a href="#2-3-区域填充算法" class="headerlink" title="2.3 区域填充算法"></a>2.3 区域填充算法</h3><blockquote>
<p>要求区域内连通</p>
</blockquote>
<p>区域可分4连通（左上右下）和8连通（斜方向）区域</p>
<ol>
<li><p>简单四连通种子填充算法（区域填充递归算法）：<br>使用栈结构来实现：栈顶像素出栈$\to$将出栈像素置成要填充色$\to$按左上右下顺序将不在边界且未填充的像素入栈填充$\to$对最后一个入栈的像素重复上述操作</p>
</li>
<li><p>多边形扫描转换算法与区域填充算法的区别<br>区域填充需要一个种子点，根据区域连通性进行颜色扩散<br>扫描线转换是从边界出发采用多种形式的连贯性进行填充</p>
</li>
</ol>
<h2 id="参考链接"><a href="#参考链接" class="headerlink" title="参考链接"></a>参考链接</h2><ol>
<li><a href="https://www.icourse163.org/learn/CAU-45006?tid=1450413503#/learn/content?type=detail&amp;id=1215011255" target="_blank" rel="noopener">中国大学MOOC</a></li>
</ol>
<script>
        document.querySelectorAll('.github-emoji')
          .forEach(el => {
            if (!el.dataset.src) { return; }
            const img = document.createElement('img');
            img.style = 'display:none !important;';
            img.src = el.dataset.src;
            img.addEventListener('error', () => {
              img.remove();
              el.style.color = 'inherit';
              el.style.backgroundImage = 'none';
              el.style.background = 'none';
            });
            img.addEventListener('load', () => {
              img.remove();
            });
            document.body.appendChild(img);
          });
      </script>

        

      
    </div>

      <!-- 相关文章推荐 -->
     

    
    
    

    <div>
          
            

          
    </div>

    

    <div>
      
        <div>
    
        <div class="read-over">-------------------本文结束 <i class="fa fa-paw"></i> 感谢您的阅读-------------------</div>
    
</div>

      
    </div>

    
      <div>
        <div class="share_reward">
  <div></div>
  <button id="rewardButton" disable="enable" onclick="var qr = document.getElementById('QR'); if (qr.style.display === 'none') {qr.style.display='block';} else {qr.style.display='none'}">
    <span>Donate</span>
  </button>
  <div id="QR" style="display: none;">

    
      <div id="wechat" style="display: inline-block">
        <img id="wechat_qr" src="/images/wechatpay.jpg" alt="戈孔明 WeChat Pay">
        <p>WeChat Pay</p>
      </div>
    

    
      <div id="alipay" style="display: inline-block">
        <img id="alipay_qr" src="/images/alipay.jpg" alt="戈孔明 Alipay">
        <p>Alipay</p>
      </div>
    

    

  </div>
</div>

      </div>
    

    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/C/" rel="tag"> <i class="fa fa-tag"></i> C++</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/p/58428.html" rel="next" title="Liang-Barsky裁剪算法">
                <i class="fa fa-chevron-left"></i> Liang-Barsky裁剪算法
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/p/12046.html" rel="prev" title="Markdown中LaTeX编写技巧">
                Markdown中LaTeX编写技巧 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
         <div data-weibo-title="分享到微博" data-qq-title="分享到QQ" data-douban-title="分享到豆瓣" class="social-share" data-disabled="qzone,google+,linkedin" data-description="Share.js - 一键分享到微博，QQ空间，腾讯微博，人人，豆瓣...">
   分享到：
</div>


      
    </div>
  </div>


          </div>
          


          

  
    <div id="gitalk-container"></div>

  





        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
      <div id="sidebar-dimmer"></div>
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            Table of Contents
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            Overview
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <a href="/">
              <img class="site-author-image" itemprop="image" src="/images/avatar.png" alt="戈孔明">
              </a>
            
              <p class="site-author-name" itemprop="name">戈孔明</p>
              <p class="site-description motion-element" itemprop="description"></p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">26</span>
                  <span class="site-state-item-name">posts</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">9</span>
                  <span class="site-state-item-name">categories</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">26</span>
                  <span class="site-state-item-name">tags</span>
                </a>
              </div>
            

          </nav>

          
            <div class="feed-link motion-element">
              <a href="/atom.xml" rel="alternate">
                <i class="fa fa-rss"></i>
                RSS
              </a>
              <!-- 为Hexo Next主题添加哈林摇特效  -->
              <a title="收藏到书签，偶尔High一下^_^" rel="alternate" class="mw-harlem_shake_slow wobble shake" href="javascript:void(0)" onclick="javascript:(    /*     * Copyright (C) 2015 Rocko (rocko.xyz) <rocko.zxp@gmail.com>     *     * Licensed under the Apache License, Version 2.0 (the 'License');     * you may not use this file except in compliance with the License.     * You may obtain a copy of the License at     *     *      http://www.apache.org/licenses/LICENSE-2.0     *     * Unless required by applicable law or agreed to in writing, software     * distributed under the License is distributed on an 'AS IS' BASIS,     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.     * See the License for the specific language governing permissions and     * limitations under the License.     */    function go() {        function c() {        var e = document.createElement('link');        e.setAttribute('type', 'text/css');        e.setAttribute('rel', 'stylesheet');        e.setAttribute('href', f);        e.setAttribute('class', l);        document.body.appendChild(e)    }     function h() {        var e = document.getElementsByClassName(l);        for (var t = 0; t < e.length; t++) {            document.body.removeChild(e[t])        }    }     function p() {        var e = document.createElement('div');        e.setAttribute('class', a);        document.body.appendChild(e);        setTimeout(function() {            document.body.removeChild(e)        }, 100)    }     function d(e) {        return {            height : e.offsetHeight,            width : e.offsetWidth        }    }     function v(i) {        var s = d(i);        return s.height > e &amp;&amp; s.height < n &amp;&amp; s.width > t &amp;&amp; s.width < r    }     function m(e) {        var t = e;        var n = 0;        while (!!t) {            n += t.offsetTop;            t = t.offsetParent        }        return n    }     function g() {        var e = document.documentElement;        if (!!window.innerWidth) {            return window.innerHeight        } else if (e &amp;&amp; !isNaN(e.clientHeight)) {            return e.clientHeight        }        return 0    }     function y() {        if (window.pageYOffset) {            return window.pageYOffset        }        return Math.max(document.documentElement.scrollTop, document.body.scrollTop)    }     function E(e) {        var t = m(e);        return t >= w &amp;&amp; t <= b + w    }     var songs = [                'http://s3.amazonaws.com/moovweb-marketing/playground/harlem-shake.mp3', 'http://www.ytmp3.cn/down/57563.mp3'  ];    function S() {        var e = document.getElementById('audio_element_id');        if(e != null){            var index = parseInt(e.getAttribute('curSongIndex'));            if(index > songs.length - 2) {                index = 0;            } else {                index++;            }            e.setAttribute('curSongIndex', index);            N();        }        e.src = i;        e.play()    }     function x(e) {        e.className += ' ' + s + ' ' + o    }     function T(e) {        e.className += ' ' + s + ' ' + u[Math.floor(Math.random() * u.length)]    }     function N() {        var e = document.getElementsByClassName(s);        var t = new RegExp('\\b' + s + '\\b');        for (var n = 0; n < e.length; ) {            e[n].className = e[n].className.replace(t, '')        }    }    function initAudioEle() {        var e = document.getElementById('audio_element_id');        if(e === null){            e = document.createElement('audio');            e.setAttribute('class', l);            e.setAttribute('curSongIndex', 0);            e.id = 'audio_element_id';            e.loop = false;            e.bgcolor = 0;            e.addEventListener('canplay', function() {            setTimeout(function() {                x(k)            }, 500);            setTimeout(function() {                N();                p();                for (var e = 0; e < O.length; e++) {                    T(O[e])                }            }, 15500)        }, true);        e.addEventListener('ended', function() {            N();            h();            go();        }, true);        e.innerHTML = ' <p>If you are reading this, it is because your browser does not support the audio element. We recommend that you get a new browser.</p> <p>';        document.body.appendChild(e);        }    }        initAudioEle();    var e = 30;    var t = 30;    var n = 350;    var r = 350;    var curSongIndex = parseInt(document.getElementById('audio_element_id').getAttribute('curSongIndex'));    var i = songs[curSongIndex];        var s = 'mw-harlem_shake_me';    var o = 'im_first';    var u = ['im_drunk', 'im_baked', 'im_trippin', 'im_blown'];    var a = 'mw-strobe_light';    var f = 'https://rocko.xyz/css/harlem-shake-style.css';        var l = 'mw_added_css';    var b = g();    var w = y();    var C = document.getElementsByTagName('*');    var k = null;    for (var L = 0; L < C.length; L++) {        var A = C[L];        if (v(A)) {            if (E(A)) {                k = A;                break            }        }    }    if (A === null) {        console.warn('Could not find a node of the right size. Please try a different page.');        return    }    c();    S();    var O = [];    for (var L = 0; L < C.length; L++) {        var A = C[L];        if (v(A)) {            O.push(A)        }    }    })()">
        <i class="fa fa-music"></i> High~
</a>

            </div>
          

          
            <div class="links-of-author motion-element">
                
                  <span class="links-of-author-item">
                    <a rel="external nofollow" href="https://github.com/gkm0120" target="_blank" title="GitHub">
                      
                        <i class="fa fa-fw fa-github"></i>GitHub</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a rel="external nofollow" href="mailto:gkm0120@163.com" target="_blank" title="E-Mail">
                      
                        <i class="fa fa-fw fa-envelope"></i>E-Mail</a>
                  </span>
                
            </div>
          

            <!--
            <div id="music163player">
                <iframe frameborder="no" border="0" marginwidth="0" marginheight="0" width=330 height=86 src="//music.163.com/outchain/player?type=2&id=1336790004&auto=1&height=66"></iframe>
            </div>
            -->

          
          
            <div class="cc-license motion-element" itemprop="license">
              <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" rel="external nofollow" class="cc-opacity" target="_blank">
                <img src="/images/cc-by-nc-sa.svg" alt="Creative Commons">
              </a>
            </div>
          

          
          
            <div class="links-of-blogroll motion-element links-of-blogroll-inline">
              <div class="links-of-blogroll-title">
                <i class="fa  fa-fw fa-link"></i>
                Links&nbsp;
                <i class="fa  fa-fw fa-link"></i>
              </div>
              <ul class="links-of-blogroll-list">
                
                  <li class="links-of-blogroll-item">
                    <a href="https://gkm0120.cn/" title="孔明の博客" rel="external nofollow" target="_blank">孔明の博客</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://hpcsiplab.hunnu.edu.cn/" title="LCSM" rel="external nofollow" target="_blank">LCSM</a>
                  </li>
                
              </ul>
            </div>
          

          <!--近期文章版块 began-->
          
          <!--近期文章版块 end-->

          
          
              <!-- 网站运行时间 -->
              <div id="days"></div>

<script language="javascript">
function show_date_time(){
window.setTimeout("show_date_time()", 1000);
BirthDay=new Date("03/15/2020 00:00:00");
today=new Date();
timeold=(today.getTime()-BirthDay.getTime());
sectimeold=timeold/1000
secondsold=Math.floor(sectimeold);
msPerDay=24*60*60*1000
e_daysold=timeold/msPerDay
daysold=Math.floor(e_daysold);
e_hrsold=(e_daysold-daysold)*24;
hrsold=setzero(Math.floor(e_hrsold));
e_minsold=(e_hrsold-hrsold)*60;
minsold=setzero(Math.floor((e_hrsold-hrsold)*60));
seconds=setzero(Math.floor((e_minsold-minsold)*60));
document.getElementById('days').innerHTML="已运行"+daysold+"天"+hrsold+"时"+minsold+"分"+seconds+"秒";
}
function setzero(i){
if (i<10)
{i="0" + i};
return i;
}
show_date_time();
</script>

          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#1-直线扫描转换算法"><span class="nav-text">1 直线扫描转换算法</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#1-1-DDA算法"><span class="nav-text">1.1 DDA算法</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#1-1-1-代码"><span class="nav-text">1.1.1 代码</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#1-1-2-运行结果"><span class="nav-text">1.1.2 运行结果</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#1-2-中点画线算法"><span class="nav-text">1.2 中点画线算法</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Bresenham算法"><span class="nav-text">Bresenham算法</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#1-3-理论"><span class="nav-text">1.3 理论</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#1-3-1-优化"><span class="nav-text">1.3.1 优化</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#1-3-2-代码"><span class="nav-text">1.3.2 代码</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#1-3-3-运行结果"><span class="nav-text">1.3.3 运行结果</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#2-多边形扫描转化算法"><span class="nav-text">2 多边形扫描转化算法</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#2-1-X扫描线算法"><span class="nav-text">2.1 X扫描线算法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#2-2-改进的X扫描线算法（不求交）"><span class="nav-text">2.2 改进的X扫描线算法（不求交）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#2-3-区域填充算法"><span class="nav-text">2.3 区域填充算法</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#参考链接"><span class="nav-text">参考链接</span></a></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

      

      <!-- 标签云 -->
      <!--
      
      <script type="text/javascript" charset="utf-8" src="/js/tagcloud.js"></script>
      <script type="text/javascript" charset="utf-8" src="/js/tagcanvas.js"></script>
      <div class="widget-wrap">
      <h3 class="widget-title">Tag Cloud</h3>
      <div id="myCanvasContainer" class="widget tagcloud">
          <canvas width="250" height="250" id="resCanvas" style="width=100%">
              <ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/AlexNet/">AlexNet</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/C/">C++</a><span class="tag-list-count">3</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Cauchy-问题/">Cauchy 问题</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Cohen-Sutherland/">Cohen-Sutherland</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/DES/">DES</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/FCN/">FCN</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/GoogLeNetV2/">GoogLeNetV2</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/GoogLeNetV3/">GoogLeNetV3</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/GoogleNetV1/">GoogleNetV1</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Hexo/">Hexo</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Hill/">Hill</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Liang-Barsky/">Liang-Barsky</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Markdown/">Markdown</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/NiN/">NiN</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Nodejs/">Nodejs</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/OpenGL/">OpenGL</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/ResNetV1/">ResNetV1</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/VGG/">VGG</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/git/">git</a><span class="tag-list-count">3</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/git配置/">git配置</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/latex/">latex</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/matlab函数/">matlab函数</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/matlab绘图/">matlab绘图</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/texlive安装/">texlive安装</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/数据集/">数据集</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/热传导方程/">热传导方程</a><span class="tag-list-count">1</span></li></ul>
          </canvas>
      </div>
      </div>
      
      -->
      <!-- 标签云 -->

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
<div class="copyright">&copy; 2020 &mdash; <span itemprop="copyrightYear">2021</span>
  <span class="with-love">
       <i class="fa fa-heartbeat"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">戈孔明</span>

  
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item-icon">
      <i class="fa fa-area-chart"></i>
    </span>
    
    <span title="Site words total count">121.3k</span>
  
</div>

<!--









-->


        
<div class="busuanzi-count">
  <!--
  <script async src="https://dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js"></script>
  -->
  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>

  
    <span class="site-uv">
      <i class="fa fa-user"></i>访问人数
      <span class="busuanzi-value" id="busuanzi_value_site_uv"></span>
      人次
    </span>
  

  
    <span class="site-pv">
      <i class="fa fa-eye"></i>总访问量
      <span class="busuanzi-value" id="busuanzi_value_site_pv"></span>
      次
    </span>
  
</div>








        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
          <span id="scrollpercent"><span>0</span>%</span>
        
      </div>
    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="//cdn.jsdelivr.net/npm/jquery@2.1.3/dist/jquery.min.js"></script>
  

  
  
    <script type="text/javascript" src="//cdn.jsdelivr.net/fastclick/1.0.6/fastclick.min.js"></script>
  

  
  
    <script type="text/javascript" src="//cdn.jsdelivr.net/jquery.lazyload/1.9.3/jquery.lazyload.min.js"></script>
  

  
  
    <script type="text/javascript" src="https://cdn.jsdelivr.net/npm/velocity-animate@1.2.1/velocity.min.js"></script>
  

  
  
    <script type="text/javascript" src="//cdn.jsdelivr.net/npm/velocity-animate@1.2.1/velocity.ui.min.js"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.4"></script>



  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.4"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.4"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  













  <link rel="stylesheet" href="https://unpkg.com/gitalk/dist/gitalk.css">
  <script src="https://unpkg.com/gitalk/dist/gitalk.min.js"></script>
  <script src="https://cdn.bootcss.com/blueimp-md5/2.10.0/js/md5.min.js"></script>
  <script type="text/javascript">
        var gitalk = new Gitalk({
          clientID: '6a4708bb548d9ee47cfd',
          clientSecret: '29a20b874fd47e6c4d1229c036d5e37beeda813d',
          repo: 'gkm0120.github.io',
          owner: 'gkm0120',
          admin: ['gkm0120'],
          id: md5(window.location.pathname),
          distractionFreeMode: 'true'
        })
        gitalk.render('gitalk-container')
       </script>



  

  <script type="text/javascript">
    // Popup Window;
    var isfetched = false;
    var isXml = true;
    // Search DB path;
    var search_path = "search.xml";
    if (search_path.length === 0) {
      search_path = "search.xml";
    } else if (/json$/i.test(search_path)) {
      isXml = false;
    }
    var path = "/" + search_path;
    // monitor main search box;

    var onPopupClose = function (e) {
      $('.popup').hide();
      $('#local-search-input').val('');
      $('.search-result-list').remove();
      $('#no-result').remove();
      $(".local-search-pop-overlay").remove();
      $('body').css('overflow', '');
    }

    function proceedsearch() {
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay"></div>')
        .css('overflow', 'hidden');
      $('.search-popup-overlay').click(onPopupClose);
      $('.popup').toggle();
      var $localSearchInput = $('#local-search-input');
      $localSearchInput.attr("autocapitalize", "none");
      $localSearchInput.attr("autocorrect", "off");
      $localSearchInput.focus();
    }

    // search function;
    var searchFunc = function(path, search_id, content_id) {
      'use strict';

      // start loading animation
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay">' +
          '<div id="search-loading-icon">' +
          '<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>' +
          '</div>' +
          '</div>')
        .css('overflow', 'hidden');
      $("#search-loading-icon").css('margin', '20% auto 0 auto').css('text-align', 'center');

      $.ajax({
        url: path,
        dataType: isXml ? "xml" : "json",
        async: true,
        success: function(res) {
          // get the contents from search data
          isfetched = true;
          $('.popup').detach().appendTo('.header-inner');
          var datas = isXml ? $("entry", res).map(function() {
            return {
              title: $("title", this).text(),
              content: $("content",this).text(),
              url: $("url" , this).text()
            };
          }).get() : res;
          var input = document.getElementById(search_id);
          var resultContent = document.getElementById(content_id);
          var inputEventFunction = function() {
            var searchText = input.value.trim().toLowerCase();
            var keywords = searchText.split(/[\s\-]+/);
            if (keywords.length > 1) {
              keywords.push(searchText);
            }
            var resultItems = [];
            if (searchText.length > 0) {
              // perform local searching
              datas.forEach(function(data) {
                var isMatch = false;
                var hitCount = 0;
                var searchTextCount = 0;
                var title = data.title.trim();
                var titleInLowerCase = title.toLowerCase();
                var content = data.content.trim().replace(/<[^>]+>/g,"");
                var contentInLowerCase = content.toLowerCase();
                var articleUrl = decodeURIComponent(data.url);
                var indexOfTitle = [];
                var indexOfContent = [];
                // only match articles with not empty titles
                if(title != '') {
                  keywords.forEach(function(keyword) {
                    function getIndexByWord(word, text, caseSensitive) {
                      var wordLen = word.length;
                      if (wordLen === 0) {
                        return [];
                      }
                      var startPosition = 0, position = [], index = [];
                      if (!caseSensitive) {
                        text = text.toLowerCase();
                        word = word.toLowerCase();
                      }
                      while ((position = text.indexOf(word, startPosition)) > -1) {
                        index.push({position: position, word: word});
                        startPosition = position + wordLen;
                      }
                      return index;
                    }

                    indexOfTitle = indexOfTitle.concat(getIndexByWord(keyword, titleInLowerCase, false));
                    indexOfContent = indexOfContent.concat(getIndexByWord(keyword, contentInLowerCase, false));
                  });
                  if (indexOfTitle.length > 0 || indexOfContent.length > 0) {
                    isMatch = true;
                    hitCount = indexOfTitle.length + indexOfContent.length;
                  }
                }

                // show search results

                if (isMatch) {
                  // sort index by position of keyword

                  [indexOfTitle, indexOfContent].forEach(function (index) {
                    index.sort(function (itemLeft, itemRight) {
                      if (itemRight.position !== itemLeft.position) {
                        return itemRight.position - itemLeft.position;
                      } else {
                        return itemLeft.word.length - itemRight.word.length;
                      }
                    });
                  });

                  // merge hits into slices

                  function mergeIntoSlice(text, start, end, index) {
                    var item = index[index.length - 1];
                    var position = item.position;
                    var word = item.word;
                    var hits = [];
                    var searchTextCountInSlice = 0;
                    while (position + word.length <= end && index.length != 0) {
                      if (word === searchText) {
                        searchTextCountInSlice++;
                      }
                      hits.push({position: position, length: word.length});
                      var wordEnd = position + word.length;

                      // move to next position of hit

                      index.pop();
                      while (index.length != 0) {
                        item = index[index.length - 1];
                        position = item.position;
                        word = item.word;
                        if (wordEnd > position) {
                          index.pop();
                        } else {
                          break;
                        }
                      }
                    }
                    searchTextCount += searchTextCountInSlice;
                    return {
                      hits: hits,
                      start: start,
                      end: end,
                      searchTextCount: searchTextCountInSlice
                    };
                  }

                  var slicesOfTitle = [];
                  if (indexOfTitle.length != 0) {
                    slicesOfTitle.push(mergeIntoSlice(title, 0, title.length, indexOfTitle));
                  }

                  var slicesOfContent = [];
                  while (indexOfContent.length != 0) {
                    var item = indexOfContent[indexOfContent.length - 1];
                    var position = item.position;
                    var word = item.word;
                    // cut out 100 characters
                    var start = position - 20;
                    var end = position + 80;
                    if(start < 0){
                      start = 0;
                    }
                    if (end < position + word.length) {
                      end = position + word.length;
                    }
                    if(end > content.length){
                      end = content.length;
                    }
                    slicesOfContent.push(mergeIntoSlice(content, start, end, indexOfContent));
                  }

                  // sort slices in content by search text's count and hits' count

                  slicesOfContent.sort(function (sliceLeft, sliceRight) {
                    if (sliceLeft.searchTextCount !== sliceRight.searchTextCount) {
                      return sliceRight.searchTextCount - sliceLeft.searchTextCount;
                    } else if (sliceLeft.hits.length !== sliceRight.hits.length) {
                      return sliceRight.hits.length - sliceLeft.hits.length;
                    } else {
                      return sliceLeft.start - sliceRight.start;
                    }
                  });

                  // select top N slices in content

                  var upperBound = parseInt('1');
                  if (upperBound >= 0) {
                    slicesOfContent = slicesOfContent.slice(0, upperBound);
                  }

                  // highlight title and content

                  function highlightKeyword(text, slice) {
                    var result = '';
                    var prevEnd = slice.start;
                    slice.hits.forEach(function (hit) {
                      result += text.substring(prevEnd, hit.position);
                      var end = hit.position + hit.length;
                      result += '<b class="search-keyword">' + text.substring(hit.position, end) + '</b>';
                      prevEnd = end;
                    });
                    result += text.substring(prevEnd, slice.end);
                    return result;
                  }

                  var resultItem = '';

                  if (slicesOfTitle.length != 0) {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + highlightKeyword(title, slicesOfTitle[0]) + "</a>";
                  } else {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + title + "</a>";
                  }

                  slicesOfContent.forEach(function (slice) {
                    resultItem += "<a href='" + articleUrl + "'>" +
                      "<p class=\"search-result\">" + highlightKeyword(content, slice) +
                      "...</p>" + "</a>";
                  });

                  resultItem += "</li>";
                  resultItems.push({
                    item: resultItem,
                    searchTextCount: searchTextCount,
                    hitCount: hitCount,
                    id: resultItems.length
                  });
                }
              })
            };
            if (keywords.length === 1 && keywords[0] === "") {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-search fa-5x" /></div>'
            } else if (resultItems.length === 0) {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>'
            } else {
              resultItems.sort(function (resultLeft, resultRight) {
                if (resultLeft.searchTextCount !== resultRight.searchTextCount) {
                  return resultRight.searchTextCount - resultLeft.searchTextCount;
                } else if (resultLeft.hitCount !== resultRight.hitCount) {
                  return resultRight.hitCount - resultLeft.hitCount;
                } else {
                  return resultRight.id - resultLeft.id;
                }
              });
              var searchResultList = '<ul class=\"search-result-list\">';
              resultItems.forEach(function (result) {
                searchResultList += result.item;
              })
              searchResultList += "</ul>";
              resultContent.innerHTML = searchResultList;
            }
          }

          if ('auto' === 'auto') {
            input.addEventListener('input', inputEventFunction);
          } else {
            $('.search-icon').click(inputEventFunction);
            input.addEventListener('keypress', function (event) {
              if (event.keyCode === 13) {
                inputEventFunction();
              }
            });
          }

          // remove loading animation
          $(".local-search-pop-overlay").remove();
          $('body').css('overflow', '');

          proceedsearch();
        }
      });
    }

    // handle and trigger popup window;
    $('.popup-trigger').click(function(e) {
      e.stopPropagation();
      if (isfetched === false) {
        searchFunc(path, 'local-search-input', 'local-search-result');
      } else {
        proceedsearch();
      };
    });

    $('.popup-btn-close').click(onPopupClose);
    $('.popup').click(function(e){
      e.stopPropagation();
    });
    $(document).on('keyup', function (event) {
      var shouldDismissSearchPopup = event.which === 27 &&
        $('.search-popup').is(':visible');
      if (shouldDismissSearchPopup) {
        onPopupClose();
      }
    });
  </script>





  

  

  
<script>
(function(){
    var bp = document.createElement('script');
    var curProtocol = window.location.protocol.split(':')[0];
    if (curProtocol === 'https') {
        bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';        
    }
    else {
        bp.src = 'http://push.zhanzhang.baidu.com/push.js';
    }
    var s = document.getElementsByTagName("script")[0];
    s.parentNode.insertBefore(bp, s);
})();
</script>


  
  
  
  <link rel="stylesheet" href="/lib/needsharebutton/needsharebutton.css">

  
  
  <script src="/lib/needsharebutton/needsharebutton.js"></script>

  <script>
    
    
  </script>

  

  
  
    <script type="text/x-mathjax-config">
      MathJax.Hub.Config({
        tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
        }
      });
    </script>

    <script type="text/x-mathjax-config">
      MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
        }
      });
    </script>
    <script type="text/javascript" src="//cdn.bootcss.com/mathjax/2.7.1/latest.js?config=TeX-AMS-MML_HTMLorMML"></script>
  


  

  


  <!-- Tidio 在线联系功能、鼠标点击特效、页面反馈...-->
  


  










  <script src="/js/src/activate-power-mode.min.js"></script>
  <script>
    POWERMODE.colorful = true;
    POWERMODE.shake = false;
    document.body.addEventListener('input', POWERMODE);
  </script>



  <!-- 看板娘 -->
  <!--  -->

  <!-- 看板娘 -->
  <script async src="/live2d-widget/autoload.js"></script>

  
      <!-- aplayer音频播放 -->
      <link rel="stylesheet" href="/dist/APlayer.min.css">
      <div id="aplayer"></div>
      <script type="text/javascript" src="/dist/APlayer.min.js"></script>
      <script type="text/javascript" src="/dist/music.js"></script>
  

  <!-- 代码块复制功能 -->
  <script type="text/javascript" src="/js/src/clipboard.min.js"></script>
  <script type="text/javascript" src="/js/src/clipboard-use.js"></script>

  <!--share.js-->
  <link rel="stylesheet" href="/sharejs/css/share.min.css">
  <script src="/sharejs/js/social-share.min.js"></script>

  <!-- 模仿知乎卡片样式链接、崩溃欺骗特效 -->
  <!--<script type="text/javascript" src="/js/src/linkcard.js"></script>-->

  <!--崩溃欺骗 放在js文件最后-->
  <!--<script type="text/javascript" src="/js/src/crash_cheat.js"></script>-->



</body>
</html>
